package two.chapter_1.c1_5;

public class QuickUnionUF extends UF {

    public QuickUnionUF(int N) {
        super(N);
    }

    @Override
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);
        if (pId != qId) {
            ids[pId] = qId;
            count--;
        }

    }

    /**
     * 访问数组的次数  最好情况  1次
     *               最坏情况  N+N-1=2N-1次
     *
     * @param p
     * @return
     */
    @Override
    public int find(int p) {
        while (ids[p] != p) {   //最坏情况// N次
            p = ids[p];          //N-1次
        }
        return p;
    }
}
